import java.util.*;

public class zuHe {
    //给你一个无重复的数字元素的数组candidates和一个目标整数target，找出candidates
    //中可以使得数字和为target的全体不同组合，通过列表的形式返回。按照任意顺序返回此类的组合

    //注意：candidates中的数字元素可以重复使用，但是实际上同一个数字可以重复使用

    static List<List<Integer>> result=new ArrayList<>();
    static LinkedList<Integer> path=new LinkedList<>();
    public static List<List<Integer>> combineSum(int[] candidates, int target){
        // 最开始确定解题的思想是：回溯遍历，对全部和为target的数字组合进行统计

        int len=candidates.length;
        if(len==0){
            return result;
        }
        int sum=0; //统计当前的遍历后累计的数字和
        backTracking(target,len,0,candidates,sum);
        return result;

    }

    private static void backTracking(int target, int len, int depth, int[] candidates, int sum){
        if(depth==len){
            return;
        }
        if(sum>target){
            return;
        }
        if(sum==target){
            result.add(new ArrayList<>(path));
            return;
        }
        //给出回溯的遍历过程
        sum+=candidates[depth];
        path.add(candidates[depth]);
        backTracking(target, len, depth, candidates, sum);
        sum-=candidates[depth];
        path.removeLast();
        backTracking(target, len, depth+1, candidates, sum);
    }

    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        System.out.print("请输入数组的长度：");
        int n=in.nextInt();
        int[] a=new int[n];
        for (int i = 0; i <n ; i++) {
            a[i]=in.nextInt();
        }
        System.out.println(Arrays.toString(a));
        System.out.print("请输入目标数字和：");
        int target=in.nextInt();
        System.out.println("得到的组合数为："+combineSum(a,target));
    }
}
